A “network,” as will be used herein, is a collection of nodes with (undirected) links between various node pairs. A “demand” of bandwidth b between a pair of nodes u and v can be thought of as a request for a reservation of bandwidth b along each link in some route between u and v. Then, as is well known to those of ordinary skill in the art, the goal of “traffic grooming” is to determine how to route each demand so as to best be able to bundle up lower bandwidth demands along a link into higher bandwidth “pipes” (i.e., channels).
Typically there are a number of different sized bandwidth pipes available, each with an associated per mile cost. The costs are typically such that the cost per unit of bandwidth per mile is cheaper on a larger bandwidth pipe. Thus, if there are sufficiently many demands routed along a given link, it will usually be cheaper to reserve a large bandwidth pipe to handle them, rather than using a large number of smaller bandwidth pipes.
Often there is an underlying physical network over which the demands must be routed. We will assume herein however that every location is directly connected to every other location. Then, the distance between two locations (i.e., nodes) is simply the Euclidean distance between them. Since the grooming problem is essentially choosing the best paths along which to route the demands, the problem clearly becomes more difficult as the number of possible paths to choose from increases. In particular, the number of simple paths (i.e., paths without cycles) between a given pair of nodes in the completely connected network case we address is exponential. Even if we restrict the number of links in a path to, for example, a number k, in a network with n nodes there are O(nk) possible paths to be considered. That is, the grooming problem can become very complex due to the large number of choices for routing each demand.
A summary of the problem being addressed herein then is as follows:
Assume that we are given demands of various bandwidths between pairs of nodes. For example, for each pair of locations, say A and B, we are given the number of DS1 (low bandwidth) circuits required between A and B and the number of DS3 (high bandwidth) circuits desired between A and B. (DS1 and DS3 circuits are fully familiar to those of ordinary skill in the art.) Since higher bandwidth pipes are typically cheaper per unit capacity per mile, the problem is to find the best (e.g., optimal) way to route these demands in order to be able to efficiently pack them into high bandwidth pipes to thereby reduce (e.g., minimize) the total cost of reserving pipes to accommodate these routings.
One simple example is as follows:
Suppose we have locations A1, A2, . . . , An on the East Coast and locations B1, B2, . . . , Bn on the West coast, and there is a single demand (of some bandwidth x) between each pair of locations Ai and Bi, for 1≦i≦n. Now suppose that the cost of connecting nodes with a “Type I” pipe having bandwidth x is a dollars per mile and that the distance between Ai and Bi is 4000 miles for 1≦i≦n. Consider now a “Type II” pipe which has higher bandwidth y=nx and which costs b dollars per mile, where b is (typically) significantly smaller than na, due to economies of scale. Suppose the distance between A1 and all other Ai is 10 miles and, similarly, the distance from B1 to all other Bi is 10 miles. Then, the straightforward solution of putting a “Type I” pipe between each Ai and Bi, 1≦i≦n, costs a total of 4000na dollars. However, we could instead connect each Ai, i>1, to A1 and each Bi, i>1, to B1 with a “Type I” pipe for a total cost of 20(n−1)a dollars, while we connect A1 to B1 with a “Type II” pipe for a cost of 4000b dollars. Thus, this alternate solution would have a total cost of 20(n−1)a+4000b dollars. So, if b is in fact significantly smaller than na this alternate solution would clearly be cheaper. The problem of reducing (e.g., minimizing) the cost of such a network is sometimes referred to as the “buy-at-bulk” problem.
(Note that in contrast to much of the buy-at-bulk literature, however, we are particularly interested here in fully connected graphs. The reason is that we are particularly motivated by the problem of purchasing bandwidth over a communications network from a communications service provider. Although the physical network operated by the service provider may have an arbitrary topology, the service provider will typically present to the customer a fully connected virtual network in which bandwidth may be purchased between any pair of nodes.)
As pointed out above, the traffic grooming problem can become very complex due to the large number of choices for routing each demand. Therefore, it would be highly desirable to have an efficient method for grooming traffic demands according to mileage based tariffs.